原文題目
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

題目摘要

1. 給定一個無序的整數數組 nums，回傳最長的連續元素序列的長度。
2. 連續元素指的是數字之間的差為 1 的序列，例如 [1, 2, 3, 4]。

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

解題思路

1. 使用 HashSet 進行數字儲存：
   • 由於問題需要檢查連續的數字，因此使用 HashSet 在常數時間內檢查某個數是否存在。這裡我們將數組中的所有數字存入 HashSet，便於後續操作。
   • 先檢查陣列是否為空，如果是空的，直接回傳 0。
2. 遍歷 HashSet 並檢查連續序列：
   • 對於每個數字，我們檢查該數字是否是某個連續序列的起點，通過檢查 num - 1 是否存在於 HashSet 來判斷當 num - 1 不存在時， num 就是一個連續序列的起點。
   • 從該起點開始，依次檢查 num + 1、num + 2 是否存在於 HashSet 中，以計算連續序列的長度。
3. 更新最長連續序列的長度：
   • 每當找到一個完整的連續序列，將當前序列的長度與之前記錄的最長序列長度進行比較，並更新 longestStreak 以保持最長的連續序列長度。
4. 回傳結果：
   • 當所有數字都被遍歷完畢後，longestStreak 中即存儲著最長的連續序列長度，最終返回該值。

程式碼

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> numSet = new HashSet<>(); //設立一個HashSet用於儲存陣列中的所有元素 
        //如果陣列為空，直接返回0
        if (nums.length == 0) {
            return 0;
        }
        
        //將陣列中的每個數字添加到HashSet中
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longestStreak = 0; //設立一個變數來儲存最長連續序列的長度
        
        //遍歷numSet中的每個數字
        for (int num : numSet) {
            //檢查當前數字是否是某個連續序列的起點
            if (!numSet.contains(num - 1)) {
                int currentNum = num; //從當前數字開始，計算連續序列的長度
                int currentStreak = 1; //當前連續序列的長度從 1 開始
                
                //繼續查找連續的數字，直到找不到為止
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1; //增加前數字
                    currentStreak += 1; //更新連續序列的長度
                }
                
                longestStreak = Math.max(longestStreak, currentStreak); //更新最長連續序列的長度
            }
        }
        
        return longestStreak; //回傳最長連續序列的長度        
    }
}

結論
這題我透過將所有數字儲存在 HashSet 中，快速查找某數字是否存在，簡化了連續序列的查找。找到連續序列的起點後，依次檢查後續數字是否存在，計算序列長度。此方法避免重複處理數字，有效控制時間複雜度，最終在 O(n) 時間內得到結果，也保持程式簡潔高效。